package JavaCode.random_records.N2401_N2600;

import utils.Parse;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author mikusugar
 * @version 1.0, 2023/3/24 14:41
 * @description N2580_count_ways_to_group_overlapping_ranges
 */
public class N2580_count_ways_to_group_overlapping_ranges {
    public static void main(String[] args) {
        //570065479
        System.out.println(new N2580_count_ways_to_group_overlapping_ranges().countWays(
                Parse.toIntTwoArr("[[57,92],[139,210],[306,345],[411,442],[533,589]," +
                        "[672,676],[801,831],[937,940],[996,1052],[1113,1156],[1214,1258],[1440,1441]," +
                        "[1507,1529],[1613,1659],[1773,1814],[1826,1859],[2002,2019],[2117,2173]," +
                        "[2223,2296],[2335,2348],[2429,2532],[2640,2644],[2669,2676],[2786,2885]," +
                        "[2923,2942],[3035,3102],[3177,3249],[3310,3339],[3450,3454],[3587,3620]," +
                        "[3725,3744],[3847,3858],[3901,3993],[4100,4112],[4206,4217],[4250,4289]," +
                        "[4374,4446],[4510,4591],[4675,4706],[4732,4768],[4905,4906],[5005,5073]," +
                        "[5133,5142],[5245,5309],[5352,5377],[5460,5517],[5569,5602],[5740,5791]," +
                        "[5823,5888],[6036,6042],[6096,6114],[6217,6262],[6374,6394],[6420,6511]," +
                        "[6564,6587],[6742,6743],[6797,6877],[6909,6985],[7042,7117],[7141,7144]," +
                        "[7276,7323],[7400,7456],[7505,7557],[7690,7720],[7787,7800],[7870,7880]," +
                        "[8013,8031],[8114,8224],[8272,8328],[8418,8435],[8493,8537],[8600,8704]," +
                        "[8766,8812],[8839,8853],[9032,9036],[9108,9189],[9222,9291],[9344,9361]," +
                        "[9448,9502],[9615,9673],[9690,9800],[9837,9868],[85,96],[145,202],[254,304]," +
                        "[372,411],[534,551],[629,692],[727,787],[861,944],[1041,1084],[1133,1174]," +
                        "[1260,1307],[1339,1358],[1478,1548],[1580,1618],[1694,1814],[1848,1891],[1936,1990],[2058,2130]]")
        ));
        System.out.println(new N2580_count_ways_to_group_overlapping_ranges().countWays(
                Parse.toIntTwoArr("[[1069,1207],[2061,2393],[2553,3287],[3834,4857],[5035,5883],[7058,7444],[7591,7895],[9284,9810],[10171,10379],[11921,12286],[13353,13420],[13943,14879],[15252,16312],[16631,17282],[17806,17992],[19391,20068],[20196,21103],[21824,22590],[23425,23454],[24895,25088],[25242,25552],[26735,27618],[27686,27815],[29798,30148],[30312,30990],[32261,32645],[32939,33848],[34762,35146],[35380,35422],[36977,37249],[38288,38959],[39281,39645],[40651,40857],[41975,42721],[43369,43778],[44691,44701],[45612,45652],[47115,47218],[48564,48779],[49433,49829],[50527,51300],[52534,52618],[53089,53862],[55014,55064],[55373,56428],[57154,57604],[58791,58873],[59531,59769],[60378,60493],[61999,62244],[63392,63637],[64646,65131],[66556,66593],[66898,67832],[68016,68674],[69276,69371],[70488,71647],[71780,71813],[73029,73279],[74782,75043],[75795,76381],[77207,77869],[78891,79032],[79504,79748],[81230,81326],[81909,82046],[83297,83638],[84453,85230],[85854,86067],[87485,87967],[88440,88912],[89293,90032],[90536,90756],[91772,92451],[93344,93985],[94693,94951],[95590,95838],[97159,97421],[99163,99261],[100248,100423],[100771,101544],[102416,102891],[103512,104070],[104516,104653],[106167,106497],[107093,107786],[108172,108294],[109715,110142],[110758,110840],[112498,112778],[113518,114128],[114411,115548],[115673,116459],[117341,117911],[118449,119155],[119508,120340],[121173,121460],[121942,122548],[123517,123715],[125035,125129],[126136,126490],[127530,128135],[128883,129396],[130015,130553],[130989,131168],[132528,132598],[133489,133861],[134502,135402],[136489,136889],[137147,137708],[138371,138529],[139851,140187],[141724,141948],[142055,142702],[143820,144148],[144651,145607],[146471,146571],[147646,148229],[148693,149186],[150041,150625],[151435,151804],[152555,153297],[154314,154441],[155254,155287],[156189,156349],[158073,158209],[159090,159419],[160329,160854],[161646,161755],[162938,162999],[163489,164136],[165113,165776],[165947,167004],[167743,167889],[168576,169141],[169881,170078],[171296,172159],[172420,172537],[173628,174181],[175129,175504],[176145,176456],[177464,177678],[178999,179112],[179934,180951],[181316,181429],[183022,183218],[184477,184479],[184933,185087],[186388,186526],[187509,187975],[188839,189615],[190145,190545],[191156,191817],[192780,193495],[194192,194514],[195567,195691],[196222,196473],[197514,198424],[198812,199812],[200799,201107],[201254,201607],[202746,203565],[204558,204755],[205682,205803],[206421,207098],[207930,208235],[208833,209008],[210167,211058],[211519,212190],[212572,212629],[214042,214475],[215190,215676],[216830,216887],[217597,218020],[219310,219943],[220473,221004],[221397,221609],[222654,223143],[224270,224504],[225527,225842],[226985,227388],[227874,228500],[229553,229712],[230687,230894],[231355,231637],[232594,233710],[233962,234115],[235375,235742],[236600,236831],[238453,238611],[239257,239372],[240204,240231],[242189,242343],[243458,243681],[243913,244589],[245390,245630],[246379,247422],[248573,248723],[249488,249692],[250847,250888],[251854,251897],[252853,253762],[254054,254081],[255261,256121],[256638,256679],[258080,258269],[259551,259920],[260949,261435],[261624,261951],[263081,263646],[264155,265128],[265904,266471],[266609,267468],[267886,268221],[269699,269994],[271121,271449],[271728,272219],[272873,272917],[274296,275157],[275704,276391],[276868,277357],[277863,278316],[279458,280061],[280937,281006],[281917,282035],[282862,283682],[284421,284932],[285528,286442],[286906,287217],[287858,288559],[289168,289856],[290655,291156],[291668,292744],[293005,293496],[294148,294328],[296065,296275],[297169,297475],[298747,299060],[299448,299504],[300531,300961],[301701,302086],[302987,302990],[304784,305046],[305480,306589],[306834,307376],[308084,308921],[309850,310204],[310612,310919],[312300,312670],[313416,313983],[314800,314855],[316043,316548],[316950,317975],[318576,318943],[319494,320008],[321057,321594],[322459,323032],[323243,324110],[324362,324913],[326514,326627],[327317,328060],[328477,329229],[329515,330080],[331144,331303],[331987,332752],[333530,333545],[335190,335340],[335717,336348],[337601,338128],[338154,338550],[339674,339761],[340672,341510],[342438,342568],[343725,344044],[344440,345090],[346628,346831],[347849,348001],[349304,349399],[350210,350434],[350992,351610],[352284,352910],[353666,354207],[354745,355474],[355805,356041],[358106,358120],[358665,359338],[359958,360238],[361115,361770],[362355,362542],[363285,363861],[365437,365667],[365896,366456],[367562,368262],[368977,368997],[370247,370487],[371266,371785],[372120,372641],[373332,374144],[374673,375010],[375905,376793],[378067,378106],[378443,378669],[379950,380812],[380914,381173],[382419,382654],[383646,383941],[385590,385628],[386295,386396],[388132,388324],[388737,388798],[390109,390768],[390944,391105],[392244,392968],[393696,393819],[394961,395431],[396046,397066],[397915,398257],[398514,398704],[399947,400055],[401818,402187],[402747,403496],[404209,404270],[405434,405975],[406959,407263],[407412,408101],[409377,409538],[410676,410708],[411042,411920],[412610,413036],[413791,414675],[415030,415480],[416513,417290],[418410,418436],[418697,419500],[419919,420111],[421117,421337],[422551,423031],[424276,424401],[425040,425645],[426574,426849],[428259,428286],[428842,429842],[430455,430841],[431981,432048],[432450,432924],[434570,434667],[434930,436035],[436460,437238],[437963,438657],[438860,439362],[440057,441127],[441426,441820],[442870,443237],[444448,444732],[445592,445883],[446386,447452],[447811,448251],[448806,449306],[450470,451054],[451287,451328],[452752,453154],[453974,454716],[455351,455959],[456919,457465],[458507,458564],[459032,459716],[460512,460998],[461703,461812],[462692,462969],[464468,464679],[465406,466028],[466588,466772],[467709,468803],[469196,469652],[470263,471077],[471669,471914],[473392,473761],[474210,475141],[475176,476034],[476479,476754],[477949,478728],[478928,478986],[480882,481349],[482088,482256],[482944,483702],[484642,484834],[485359,486303],[487600,487688],[488445,488521],[489556,490144],[490282,491457],[492263,492355],[492948,493911],[494676,495080],[496161,496256],[497408,497435],[498139,498244],[499375,499671],[501050,501121],[501747,501752],[503214,503644],[504157,504387],[505421,505800],[506761,507176],[507902,508781],[509398,509776],[511177,511471],[511623,512832],[512941,513475],[514458,514857],[515764,515865],[516891,516978],[518014,518256],[519267,520238],[520744,521599],[522558,522658],[523913,524149],[524900,525137],[526247,526506],[526947,527180],[528065,528368],[529455,529983],[530862,531550],[531720,531731],[533260,533275],[534554,535155],[535571,535865],[537642,537691],[537998,538379],[539944,540234],[541103,541588],[542011,542451],[543280,543740],[544806,544964],[546187,546558],[547220,547449],[548574,548817],[549548,549853],[550636,550744],[551869,552087],[554069,554091],[555183,555235],[555851,556099],[557334,557660],[558670,558697],[560284,560520],[561103,561115],[562245,563063],[563465,563705],[564713,565251],[566393,566411],[567345,567628],[568547,569177],[569955,570634],[571247,571410],[572523,573050],[574004,574362],[574614,575079],[576076,576809],[577765,578132],[578310,578922],[579873,580721],[580807,581809],[583053,583180],[583718,583914],[585101,585236],[586494,586868],[587654,587965],[588278,589303],[590303,590477],[591008,591839],[592711,593163],[593559,594452],[595093,595438],[595846,596357],[597795,597911],[598640,598732],[600241,600772],[601509,602070],[602167,603227],[603804,604508],[604987,605814],[606628,606667],[607316,608140],[608778,609019],[610035,610764],[611003,611174],[612555,612791],[614241,614304],[614940,615432],[616176,616796],[618314,618342],[618615,618816],[620010,620013],[621917,621959],[622592,622686],[623789,624707],[624772,625389],[626204,627084],[628230,628261],[628617,628879],[629793,629795],[631076,631461],[632332,632666],[634460,634548],[635366,635735],[636804,637118],[638263,638375],[638932,639199],[640492,640576],[641397,641900],[642592,642645],[643626,644156],[645013,645456],[646201,647312],[647543,648466],[649264,649645],[649886,650483],[651199,651885],[653201,653251],[654120,654604],[655363,655593],[656636,656858],[658248,658339],[658961,659058],[660093,660896],[661367,662161],[662654,663111],[664330,664513],[665611,666025],[667059,667424],[667878,667931],[669126,669414],[670334,671077],[672283,672459],[672860,672953],[674321,674699],[675188,675381],[676568,677444],[678420,678541],[679407,679599],[680062,681109],[681595,681953],[683158,683194],[683889,684901],[685203,685941],[686434,686477],[688090,688610],[689066,689484],[690171,690502],[691705,691992],[692861,693548],[693943,694511],[695782,695930],[696688,697016],[697667,698466],[699211,699334],[700855,701337],[701426,701770],[703412,703753],[704719,704941],[706091,706200],[707144,707211],[708770,708867],[709290,710095],[710248,710671],[711619,712315],[713730,713938],[714685,715056],[715963,716187],[717014,717601],[717832,718739],[719079,719748],[720805,721075],[721638,722351],[723423,723658],[724235,724872],[725707,726008],[726678,727198],[727896,728730],[729235,729717],[730467,730908],[732488,732645],[732996,733987],[734524,735056],[735605,736246],[737478,737585],[738072,738182],[739286,739595],[740808,741380],[741898,742371],[743267,743915],[744167,744185],[745556,745568],[746753,747414],[747951,748950],[749511,749897],[750901,751505],[752071,752377],[753238,753995],[754324,755226],[755661,755805],[756947,757582],[758137,758387],[759954,760442],[760829,761382],[762740,762915],[763798,763904],[764476,764642],[765895,766122],[767063,767764],[768453,768902],[769524,769984],[770950,771548],[771804,772566],[773061,773620],[774792,775029],[775578,775863],[777836,778067],[778104,778913],[779708,780504],[780675,781325],[782119,782384],[783903,784118],[784662,785453],[786073,786291],[787915,788073],[789117,789135],[789557,790316],[791289,791342],[791917,792730],[793885,794414],[794641,794679],[796037,796725],[796980,797033],[798246,799078],[799733,800618],[800746,801854],[802534,802964],[803419,803852],[804870,805370],[805774,806136],[807130,807528],[808589,809392],[809735,810132],[810842,811801],[812886,812917],[813796,813923],[814822,815403],[817017,817027],[817528,818079],[818404,819163],[820045,820698],[820988,821766],[822160,823180],[823771,824003],[824920,825497],[825962,826628],[827171,827832],[828721,828841],[829963,830827],[830932,831751],[832959,833244],[833429,834446],[835595,835617],[836549,837138],[837162,838305],[838839,839610],[839916,840709],[841102,841277],[843157,843335],[843594,844297],[844757,845365],[846177,847001],[848144,848333],[848883,849272],[849828,849971],[851751,851975],[852300,852425],[853862,854425],[855365,855953],[856333,857254],[858212,858321],[859021,859222],[860782,860869],[861871,861876],[862802,862930],[863639,863999],[864933,864938],[866507,866932],[868415,868478],[868681,869330],[870126,870785],[871896,871898],[872865,872920],[874141,874304],[875318,875457],[876435,877283],[877678,877878],[879761,879896],[880879,881105],[882222,882259],[883001,883549],[884182,884501],[885191,886153],[886686,887117],[887756,888009],[889252,889527],[890521,890971],[892137,892260],[893021,893174],[894367,894412],[895337,895581],[896318,896956],[897540,898138],[898949,899561],[900329,900359],[901308,902242],[902644,902697],[903863,904082],[905053,906260],[906346,906579],[907590,908300],[908951,909254],[910313,910815],[911608,912144],[912875,913359],[913952,914082],[915265,916205],[916406,916944],[918346,918689],[918961,919854],[920149,920599],[921796,922593],[922919,922942],[924243,924387],[925286,925894],[927433,927521],[928382,928613],[929475,929479],[930874,931103],[931968,932571],[933466,933574],[934240,934425],[935357,936001],[937540,937708],[938907,938973],[939264,939275],[941211,941433],[942534,942667],[943033,943382],[944205,944488],[945363,946098],[946943,947778],[948190,948301],[949177,949377],[950628,950794],[951587,952614],[952995,953413],[955037,955267],[955647,956331],[957030,957114],[958442,958638],[959631,960233],[961086,961448],[962416,962810],[963833,963969],[964601,964776],[965455,965905],[966687,967114],[968138,968793],[969425,969707],[971130,971440],[972556,972847],[973153,973800],[974303,974925],[975649,976512],[976870,977880],[978026,978150],[979392,980267],[980703,980837],[981836,982330],[983167,983872],[985275,985365],[986367,986543],[987762,987873],[988720,989207],[989809,990174],[990747,991321],[992533,992802],[993095,994283],[994475,995090],[996419,996653],[997754,997871],[998877,999027],[156,955],[1718,2358],[2606,3598],[4566,4954],[5489,5774],[7005,7535],[8328,8577],[8805,9542],[10689,10952],[11339,12507],[13272,13612],[14188,14483],[15161,15321],[17017,17037],[17945,18198],[18858,19271],[21045,21334],[21662,22353],[22646,22778],[24055,24139],[26188,26343],[26493,26738],[27895,28751],[28945,29781],[30427,30540],[31968,32210],[32868,32996],[34107,34491],[35363,36424],[36817,37652],[38097,38777],[39410,40123],[41267,41465],[41886,42608],[42941,43060],[44123,44191],[45496,45712],[47437,47546],[47784,48976],[49242,50148],[51370,51422],[51830,52767],[53700,53839],[54287,55218],[55357,55425],[57055,57336],[57984,58928],[59872,59975],[60618,61352],[61779,62453],[63197,63275],[64619,65091],[65390,66528],[66803,66950],[68427,69025],[69537,69883],[70523,71495],[71965,72378],[73105,74073],[75247,75314],[76099,76443],[76714,77061],[78049,78346],[79863,80334],[81036,81388],[81984,82649],[83437,83627],[84291,85370],[85746,85876],[86756,87473],[88142,88228],[89360,89510],[90597,91097],[92859,92864],[94056,94138],[94282,94395],[95772,96422],[97595,97662],[98923,99227],[99627,100381],[101237,101436],[102088,102579],[103339,104144],[104489,104712],[106375,106409],[107367,107431],[109056,109201],[110292,110382],[111650,111821],[112041,112980],[113157,113854],[114531,115119],[116123,116693],[117162,117405],[119002,119061],[119711,120088],[121126,121908],[122220,122663],[123502,124104],[124723,125069],[126208,126815],[127315,127908],[128571,129127],[129646,130337],[130871,131286],[132622,132699],[133475,133499],[134642,134643],[136164,136945],[137727,137891],[138655,139319],[139798,140048],[141034,141559],[142278,142697],[144099,144225],[144885,145348],[145988,147057],[147946,148148],[148468,149550],[149809,150230],[152034,152049],[152831,153180],[154174,154421],[155197,155375],[156550,156852],[157889,158051],[159104,159332],[159759,159949],[162111,162139],[162202,162822],[163540,164091],[165107,165834],[166621,166633],[167224,167449],[169083,169274],[170019,170370],[171391,172005],[172288,173107],[173649,174457],[174908,175676],[176607,176701],[178413,178434],[178736,179569],[179871,180354],[181107,181623],[183076,183489],[183710,184734],[184863,185541],[186064,187221],[188043,188473],[188792,189747],[190617,190942],[192166,192186],[192754,192781],[193712,194504],[194983,195012],[196513,196798],[197672,198578],[199164,199728],[200747,200945],[201938,202122],[202642,202787],[203710,204415],[205220,205987],[206272,206407],[207572,207692],[208930,209894],[210963,211163],[211301,212186],[212511,213565],[214660,214695],[215190,215816],[216473,216655],[218241,218296],[219486,219556],[220555,221206],[222262,222439],[223529,223708],[223852,224382],[225223,226007],[226752,227201],[228603,228652],[228881,229328],[230507,230527],[231672,232437],[232571,233753],[234063,234959],[235937,236219],[236480,237425],[237666,238539],[239841,239894],[240185,240743],[242355,242487],[242649,242911],[244362,244596],[245412,245597],[247178,247605],[248149,248657],[249445,249997],[250427,250713],[251505,252560],[252722,253523],[254839,254986],[255306,255880],[256980,257659]]")
        ));
    }

    public int countWays(int[][] ranges) {
        final int MOD = (int) (Math.pow(10, 9)) + 7;
        Arrays.sort(ranges, Comparator.comparingInt(o -> o[0]));
        int right = ranges[0][1];
        int res = 2;
        for (int[] range : ranges) {
            if (range[0] > right) {
                res = res * 2 % MOD;
            }
            right = Math.max(right, range[1]);
        }
        return res;
    }


}
/*
给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。

你需要将 ranges 分成 两个 组（可以为空），满足：

每个区间只属于一个组。
两个有 交集 的区间必须在 同一个 组内。
如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。

比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。
请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 109 + 7 取余 后返回。

 

示例 1：

输入：ranges = [[6,10],[5,15]]
输出：2
解释：
两个区间有交集，所以它们必须在同一个组内。
所以有两种方案：
- 将两个区间都放在第 1 个组中。
- 将两个区间都放在第 2 个组中。
示例 2：

输入：ranges = [[1,3],[10,20],[2,5],[4,8]]
输出：4
解释：
区间 [1,3] 和 [2,5] 有交集，所以它们必须在同一个组中。
同理，区间 [2,5] 和 [4,8] 也有交集，所以它们也必须在同一个组中。
所以总共有 4 种分组方案：
- 所有区间都在第 1 组。
- 所有区间都在第 2 组。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 1 个组中，[10,20] 在第 2 个组中。
- 区间 [1,3] ，[2,5] 和 [4,8] 在第 2 个组中，[10,20] 在第 1 个组中。
 

提示：

1 <= ranges.length <= 105
ranges[i].length == 2
0 <= starti <= endi <= 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-ways-to-group-overlapping-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
